/*
 * topological-hex, a program to compute combinatorial hexahedral meshes.
 *
 * Copyright (C) <2018> <Université catholique de Louvain (UCL), Belgique>
 *
 * List of the contributors to the development, description and complete
 * License: see LICENSE file.
 *
 * This program (topological-hex) is free software:
 * you can redistribute it and/or modify it under the terms
 * of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (see COPYING file).  If not,
 * see <http://www.gnu.org/licenses/>.
 */

#include "dual.h"
#include <string.h>
#include <stdio.h>

static size_t quad_edge_id(quad_edge edge) {
  return 4 * quad_edge_quad(edge) + quad_edge_edge(edge);
}

/**
 * Tags every edge along a dual chord as belonging to loop_id.
 * This function ends early if a self-intersection is found.
 *
 *
 * @return True if the chord intersects itself, false otherwise.
 */
static
bool follow_loop(const quad_edge *adjacency, quad_edge start,
                 uint8_t *tags, uint8_t loop_id) {
  size_t start_id = quad_edge_id(start);

  if (tags[start_id] == loop_id)
    return false;

  quad_edge cur = start;
  do {
    tags[quad_edge_id(cur)] = loop_id;

    quad_edge next = next_edge(cur);
    if (tags[quad_edge_id(next)] == loop_id)
      return true;

    quad_edge opposite = opposite_edge(cur);

    size_t id = quad_edge_id(opposite);
    tags[id] = loop_id;
    cur = adjacency[id];
  } while (cur != start);

  return false;
}

bool dual_contains_self_intersection(const solver *solver) {
  uint8_t tags[UINT8_MAX * 4];
  memset(tags, UINT8_MAX, 4 * solver->num_quads * sizeof(*tags));

  uint32_t n_tags = 0;
  uint32_t num_quads = 0;

  for (uint32_t i = solver->quad_queue_offset;
       i < solver->quad_queue_size; i++) {
    quad_index q = solver->quad_queue[i];
    if (solver->num_occurrences[q] != 1) continue;

    num_quads++;

    for (quad_edge_index j = 0; j < 4; j++) {
      if (tags[4 * q + j] == UINT8_MAX) {
        if (follow_loop(solver->quad_adjacency,
                         make_quad_edge(q, j),
                         tags, n_tags++))
          return true;
      }
    }
  }

  return false;
}
